| 12345678910111213141516171819202122232425262728293031323334353637383940 |
- from __future__ import absolute_import, division, unicode_literals
- try:
- from collections.abc import Mapping
- except ImportError: # Python 2.7
- from collections import Mapping
- class Trie(Mapping):
- """Abstract base class for tries"""
- def keys(self, prefix=None):
- # pylint:disable=arguments-differ
- keys = super(Trie, self).keys()
- if prefix is None:
- return set(keys)
- return {x for x in keys if x.startswith(prefix)}
- def has_keys_with_prefix(self, prefix):
- for key in self.keys():
- if key.startswith(prefix):
- return True
- return False
- def longest_prefix(self, prefix):
- if prefix in self:
- return prefix
- for i in range(1, len(prefix) + 1):
- if prefix[:-i] in self:
- return prefix[:-i]
- raise KeyError(prefix)
- def longest_prefix_item(self, prefix):
- lprefix = self.longest_prefix(prefix)
- return (lprefix, self[lprefix])
|
